package main

func quicksort(nums []int) {
	if len(nums) < 2 {
		return
	}
	i := partition(nums)
	quicksort(nums[:i])
	quicksort(nums[i+1:])
}

func partition(nums []int) int {
	p := nums[0]
	i := 0
	j := len(nums) - 1
	for i < j {
		for nums[j] >= p && i < j {
			j--
		}
		for nums[i] <= p && i < j {
			i++
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[0], nums[i] = nums[i], nums[0]
	return i
}

func main() {
	nums := []int{6, 5, 2, 7, 3, 9, 8, 4, 10, 1}
	//i := partition(nums)
	//println(i)
	quicksort(nums)
	println(nums)
}
